package com.mccken.practice.top100.Top_1$20.Top_19;

/**
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2024-01-06 16:51
 **/
public class SearchMatrix {

	/*
		二分法，直接对每一层做二分法搜索，比暴力要快而已
	 */
	public boolean searchMatrix(int[][] matrix, int target) {
		for (int[] row : matrix) {
			int index = search(row, target);
			if (index >= 0) {
				return true;
			}
		}
		return false;
		
	}

	private int search(int[] nums, int target) {
		int low = 0,high = nums.length-1;
		while (low<=high) {
			int mid = (high - low) / 2 + low;
			int num = nums[mid];
			
			if (num == target) {
				return mid;
			} else if (num > target) {
				high = mid - 1;
			} else {
				low = mid+1;
			}
		}
		return -1;
	}

	/*
	    Z字型，初始定位比较重要，直接找一个角，右上角或者左下角
	    先让元素走一边，比如右上角，如果小于target，就只能让x往回走，如果大于target，就只能让y往下走，然后不走回头路
	    
	 */
	public boolean searchMatrix1(int[][] matrix, int target) {
		int m = matrix.length;
		int n = matrix[0].length;

		int x = 0, y = n - 1;
		while (x < m && y >= 0) {
			if (matrix[x][y] == target) {
				return true;
			}
			
			if (matrix[x][y] > target) {
				y--;
			} else {
				x++;
			}
		}
		return false;
	}
}
